package com.kehao.leetcode.algorithm;

import org.junit.Test;

//https://leetcode-cn.com/problems/coin-change-2/
public class Solution518 {

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];

        dp[0] = 1;
        for (int i =0; i <coins.length; i++){
            for (int j = coins[i]; j<amount+1 && j-coins[i]>=0; j++) {
                dp[j] = dp[j]+ dp[j-coins[i]];
            }
        }
        return dp[dp.length-1];
    }


    @Test
    public void myTest01(){
        int amount = 5;
        int[] coins = {1, 2, 5};
        System.out.println(change(amount, coins));
    }

    @Test
    public void myTest02(){
        int amount = 5;
        int[] coins = {2,5};
        System.out.println(change(amount, coins));
    }

    @Test
    public void myTest03(){
        int amount = 10;
        int[] coins = {10};
        System.out.println(change(amount, coins));
    }

    @Test
    public void myTest04(){
        int amount = 3;
        int[] coins = {2};
        System.out.println(change(amount, coins));
    }
}
